package com.singzi.leetcode.N100;

public class T0052 {
    public static void main(String[] args) {
        Solution10052 solution10052 = new Solution10052();
        int []nums = {-8,3,-5,-3,-5,-2};

        System.out.println(solution10052.largestSumAfterKNegations(nums, 6));

    }
}
class Solution10052 {
    public int largestSumAfterKNegations(int[] nums, int k) {

        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int min1 = -999;
        for (int i = 0; i < k; i++) {
            int sub = getMin(nums);
            if(sub >=0){
                if((k-i)%2==0) {
                    break;
                }

                else {
                    if(sub>-min1){
                        sum+=2*min1;
                    }
                    else{
                        sum -=2*sub;
                    }
                }
            }
            else {
                min1 = sub;
                sum -=2*sub;
            }
        }
        return  sum;

    }

    public int getMin(int[]nums){
        int min = 999;
        int index = 0;
        for (int i = 0; i < nums.length;i++) {
            if(nums[i]<min){
                min = nums[i];
                index = i;
            }
        }
        nums[index] = 999;

        return min;

    }
}
